package com.hardy.basic;

import com.hardy.leecode.model.ListNode;

/**
 * Author: Hardy
 * Date:   2021/1/20
 * Description:
 **/
public class Linked {

    // 单链表快排
    public ListNode fastSort1(ListNode head, ListNode end) {
        /**
         * p、q 同时偏移
         *
         * q.v < v >> p.v > v  停止 交换 p.v <=> q.v
         */
        if (head == end) return head;

        int v = head.val;
        ListNode p = head;
        ListNode q = head.next;

        while (q != end) {
            if (q.val < v) {
                p = p.next;

                // 触发交换
                if (p.val >= v) {
                    int t = q.val;
                    q.val = p.val;
                    p.val = t;
                }
            }
            q = q.next;
        }

        head.val = p.val;
        p.val = v;

        fastSort1(head, p);
        fastSort1(p.next, end);

        return head;
    }

    // 单链表归并排
    public ListNode fastSort2(ListNode head, ListNode end) {
        if (head == end) {
            if (head != null) head.next = null;
            return head;
        }

        ListNode p = head;
        ListNode q = head;

        // 拆分
        while (q != end && q.next != end) {
            p = p.next;
            q = q.next.next;
        }

        // 递归
        ListNode n1 = fastSort2(head, p);
        ListNode n2 = fastSort2(p.next, end);

        ListNode h = new ListNode(0);
        ListNode n = h;

        while (n1 != null && n2 != null) {
            if (n1.val < n2.val) {
                n.next = n1;
                n1 = n1.next;
            } else {
                n.next = n2;
                n2 = n2.next;
            }
            n = n.next;
        }
        n.next = n1 == null ? n2 : n1;
        return h.next;
    }

    // 找链表中心
    public ListNode searchCenter(ListNode head) {
        // 1 2 3 4 5  -> s = 3
        // 1 2 3 4    -> s = 2
        ListNode s = head;
        ListNode f = head.next;

        while (f != null && f.next != null) {
            s = s.next;
            f = f.next.next;
        }
        return s;
    }

    // 链表反转
    public ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode node = head;

        while (node != null) {
            ListNode next = node.next;

            node.next = prev;
            prev = node;
            node = next;
        }
        return prev;
    }

    // 链表回文检查
    public boolean check(ListNode head) {
        // 查找中心
        ListNode center = searchCenter(head);

        // 反转链表
        ListNode reverse = reverse(center.next);

        // 比较
        while (reverse != null) {
            if (head.val != reverse.val) return false;
            reverse = reverse.next;
            head = head.next;
        }
        return true;
    }

    // 19. 删除链表的倒数第 N 个结点
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int c = 1;
        ListNode temp = new ListNode(-1, head);
        ListNode p = temp;
        ListNode q = head;

        for (; q.next != null; q = q.next) {
            if (c < n) {
                c++;
            } else {
                p = p.next;
            }
        }
        p.next = p.next.next;
        return temp.next;
    }

    // 24. 两两交换链表中的节点
    public ListNode swapPairs(ListNode head) {
        ListNode temp = new ListNode(-1, head);
        ListNode p = temp;
        ListNode q = head;

        for(; q != null && q.next != null; p = q, q = q.next) {
            p.next = q.next;
            q.next = q.next.next;
            p.next.next = q;
        }
        return temp.next;
    }

    // 82. 删除有序链表中重复出现的元素
    public ListNode deleteDups(ListNode head) {
        ListNode temp = new ListNode(-1, head);

        ListNode prev = temp;
        ListNode n = head;

        while (n.next != null) {
            if (prev.next.val != n.next.val) {
                if (prev.next == n) {
                    prev = prev.next;
                } else {
                    prev.next = n.next;
                }
            }
            n = n.next;
        }
        if (prev.next != n) prev.next = n.next;

        return temp.next;
    }

    public ListNode deleteDuplicates(ListNode head) {
        ListNode current = head;
        while (current != null && current.next != null) {
            if (current.next.val == current.val) {
                current.next = current.next.next;
            } else {
                current = current.next;
            }
        }
        return head;
    }

    public ListNode gen() {
        //int[] a = {-1, 5, 3, 4, 0};
        //int[] a = {1, 2, 3, 5, 6, 6, 5, 3, 2, 1};
        int[] a = {1, 2, 2, 3, 4, 5, 5};

        ListNode head = null;
        ListNode node = null;

        for (int v : a) {
            if (head == null) {
                head = new ListNode(v);
                node = head;
            } else {
                node.next = new ListNode(v);
                node = node.next;
            }
        }
        return head;
    }

    public static void main(String[] args) {
        Linked linked = new Linked();
        ListNode head = linked.gen();

        //System.out.println(linked.fastSort1(head, null).toString());
        //System.out.println(linked.fastSort2(head, null).toString());
        System.out.println(linked.deleteDups(head));
    }
}
